Problem statement: zenit15ckd

Dole kopcom

Počet bodov: 25, časový limit: 300ms

Máme veľký 2D kváder \(r \times s\) dielikov veľký. V tomto 2D kvádri sú nasypané malé 2D kocky veľkosti \(1*1\). Kváder sa začne kotúľať dole 2D kopcom (doľava) a po \(n\) prekopŕcnutiach zastane. Samozrejme, kocky pri každom prekopŕcnutí spadnú na spodnú stranu. Ako to v kvádri bude vyzerať, keď zastane? Kde budú malé kocky?

Vstup a výstup

Na prvom riadku vstupu dostanete dve čísla \(r\) a \(s\) \((1 \leq r, s \leq 100)\) oddelené medzerou – rozmery 2D kvádra.

Na ďalšom riadku bude \(n\) \((1 \leq n \leq 1\,000\,000)\) – počet prekopŕcnutí.

Po tom nasleduje \(s\) čísel – počty kociek v jednotlivých stĺpcoch zľava doprava. Všetky kocky na začiatku podliehajú gravitácii a nachádzajú sa dole – t.j. nepadajú.

Na jediný riadok výstupu uveďte počty kociek v stĺpcoch zľava doprava, v stave, v akom budú po \(n\) preklopeniach. Aspoň polovicu bodov môžete získať za riešenie, ktoré si hravo poradí so vstupom, v ktorom počet prekopŕcnutí, \(n\), bude nanajvýš \(10\).

Kváder sa kotúľa

Príklady

Input:

5 2
1
0 3

Output:

0 0 1 1 1

Input:

4 3
2
4 1 2

Output:

1 2 4

Input:

18 11
1
0 5 0 0 13 1 2 2 2 3 1

Output:

0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 3 6 8

Tento vstup zodpovedá obrázku vyššie.